У меня на Ubuntu 11.04 соеденение по ssh с сервером в сети происходило по 20 секунд.
дебаг режим (параметр -v) ssh name@host показал попытку ssh найти kerberos сервер.Так как kerberos авторизация мне совсем не нужны, ее пришлось отключить.
Берем файл /etc/ssh/ssh_config и убираем комментарии со строчек, запрещащих GSSAPI
Host *
# ForwardAgent no
#
(
Read more... )