Pictnotes

ssh の接続が遅い場合

http://www.openssh.org/ja/faq.html
にかいてありました。

3.3 – ssh(1) が接続する、あるいはログインするのに時間がかかる。
ひじょうに長い遅延 (10秒以上) はふつうホストの名前解決によってひきおこされます:
* glibc のいくつかのバージョン (とくに Red Hat Linux 6.1 に付いている glibc) では、ドメイン名から “IPv6 あるいは IPv4 の” アドレスを解決するのに時間がかかります。この問題は、ssh_config 設定ファイルで AddressFamily inet を加えることでとりあえず解決することができます。
* クライアント側あるいはサーバ側の DNS の参照に問題がある場合もあります。クライアント側とサーバ側で nslookup コマンドを使って、お互いの名前と IP アドレスを検索してみてください。さらに、クライアントの IP 名検索で返された名前をサーバ側で検索します。 sshd_config 設定ファイルに UseDNS no を加えることでほとんどのサーバ側の DNS 検索を抑えることができます。

ということで、/etc/ssh/sshd_config に

UseDNS no
AddressFamily inet

を追記して、sshdを再起動。それぞれ、コメントアウト行があったのでその下に
追記しました。