As others have said, this is likely a DNS resolution problem.
For future reference, note that the OpenSSH FAQ describes this problem under '3.3 - ssh(1) takes a long time to connect or log in'. There are a few other possible causes, but DNS resolution is the most common issue:
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
Some admins set
UseDNS no as a protection against DNS Spoofing. For example, see the book SSH, the Secure Shell, 2nd Edition, section '10.3.3.4 TCP/IP settings' by O'Reilly, which says:
We also disable reverse DNS lookups on incoming connections:
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 [126.96.36.199].
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