Об этом писалось сотни раз, но мало ли, вдруг сто первый поможет решить проблему.

Запустите ssh к серверу с ключом -v ssh -v user@host если вы увидите, что наибольшее время проходит на этой строчке: debug1: SSH2_MSG_SERVICE_ACCEPT received то смело прописывайте в /etc/ssh/sshd_config параметр UseDNS no Если проблема сохраняется и после этого - можете попробовать отключить GSS Auth.