というので困っている人は結構いるみたいで…。
結局、Reverse DNS Lookup を Client がしているのが問題みたいだ。
しょうがないので、/etc/hosts に SSH 先の IP Address とホスト名を記入。
一瞬で繋がるようになった。
＃ちなみに、Windows からは、何の問題も無く繋がっていた…。
参考記事：http://macnewbie.wordpress.com/2006/08/30/slow-ssh-connections-on-mac-os-x/
＃要は、ssh server の reverse lookup がダメになっていたという、そういう話でした。
＃その後、DNSの設定をちゃんとしてOKになりました。