As vezes acontece de você tentar fazer o login em algum servidor linux e o mesmo demorar para responder, isso acontece porque na maioria das vezes o servidor está resolvendo o dns reverso.
Portanto se você tiver com algum problema de dns, esta resposta pode demorar ainda mais.
Para melhorar essa velocidade basta fazer as seguintes alterações no servidor.
vim /etc/ssh/sshd_config
Descomente a linha
#UseDNS yes
e troque para no
UseDNS no
reinicie o servidor ssh:
/etc/init.d/ssh restart
Isto já irá melhorar a conexão, se você continuar com problemas de velocidade na resposta experimente adicionar no resolv.conf a seguinte opção:
vi /etc/resolv.conf options single-request-reopen