Ubuntu DesktopとかUbuntu ServerにSSHで接続すると、他のディストリビューションよりも遅いと感じる件ですが、UbuntuのSSHDのデフォルト設定でGSSAPI 認証が有効化されているためなんだそうです。
GSSAPIAuthentication
GSSAPI ベースの認証をおこなうかどうかを指定します。デフォルトの値は"no"です。注意: この項目はプロトコル バージョン 2 にのみ適用されます。
と、こちらに書かれていますね。上流のsshd_configはnoですが、Ubuntuのそれはyesになっているようです。Ubuntu単体で使う場合は不要なのでこちらの情報を参考に、次のように設定してみました。結果、パスワードを入れてから接続されるまでの時間が短縮されましたよ。
$ sudo vi /etc/ssh/sshd_config
...
GSSAPIAuthentication yes
↓
GSSAPIAuthentication no$ sudo service ssh restart
これで他のディストリビューション並にコネクションが速くなりました。
ちなみに次のようなことをしたい場合はこの設定を変更すべきではないので一応いっておきます。