Decidi fazer esse pequeno guia para quem usa conexão ssh e enfrenta uns 10 segundos para poder digitar a senha de acesso ssh. O problema está relacionado com o DNS, onde o OpenSSH tenta negociar com o servidor. Resolvendo:

Edite o arquivo:
/etc/ssh/sshd_config

Caso o parametro
#UseDNS no
esteja comentado, retire o ‘#’. Caso não esteja, adicione no fim do arquivo, salve e reinicie o ssh.

sudo /etc/init.d/ssh restart

Pronto, lentidão resolvida.