>>508
ってことはやっぱsshdかsshクライアントの設定の問題かな。
/etc/sshd_config /etc/ssh_config あたりの設定の見直しと
ssh -v, ssh -vv, ssh -vvv あたりで繋げてみて怪しいメッセージとかどこで時間がかかっているかチェック。
可能であればやtcpdumpやwiresharkで怪しいパケットが飛んでないか確認。
あとはtrussでシステムコールにかかる時間計測ぐらいかね。