Como outros disseram, esse é provavelmente um problema de resolução de DNS.
Para referência futura, note que o FAQ do OpenSSH descreve este problema em ' 3.3 - ssh (1) leva muito tempo para conectar ou logar '. Existem algumas outras causas possíveis, mas a resolução de DNS é o problema mais comum:
There may be a DNS lookup problem, either at the client or server. You
can use the nslookup command to check this on both client and server
by looking up the other end's name and IP address. In addition, on the
server look up the name returned by the client's IP-name lookup. You
can disable most of the server-side lookups by setting UseDNS no in
sshd_config.
Alguns administradores definem UseDNS no
como proteção contra falsificação de DNS. Por exemplo, consulte o livro SSH, o Secure Shell, 2ª edição, seção '10 .3.3.4 Configurações TCP / IP ' da O'Reilly, que diz:
We also disable reverse DNS lookups on incoming connections:
# OpenSSH
UseDNS no
You might think security is increased by reverse DNS lookups, but in fact, DNS isn’t
secure enough to guarantee accurate lookups. Also, due to other issues in your Unix and
network environment, reverse DNS mappings might not even work properly [5.3.3.8].
Finally, SSH connections can be tremendously slowed down or fail altogether if the
client's DNS is hosed (e.g., lots of nameservers, all unresponsive, so sshd times out).
The IP addresses of connecting hosts end up in your logs anyway, so you can look them up
later.