ssh login password prompt slowly on Linux

If you're using host names (e.g., "ssh host.example.com") then you must have proper forward and reverse DNS resolution at both ends. There are ways to avoid this:

1) Add "UseDNS no" to /etc/ssh/sshd_config on the server and /etc/ssh/ssh_config on the client; or

2) Set up a DNS server with proper forward and reverse ("in-addr.arpa") records for both the client and server; or

3) Create entries in the hosts file on both the client and server with the appropriate names and addresses; or

4) Use IP addresses rather than names.

Most of the time when you have a long delay in connecting via ssh to a system it is DNS related. This is talked about in the OpenSSH FAQ item 3.3: http://www.openssh.org/faq.html#3.3

By default sshd will do a reverse look-up on the incoming IP of a connection and this can cause delays if your systems IP address (IPv4 or IPv6) is not DNS resolvable.

The usual work around is to add "UseDNS no" to the sshd_config.

Beyond the reverse dns lookup issue mentioned, another setting that some people find helps is "GSSAPIAuthentication no" in /etc/ssh/ssh_config on the client.

Reference:
http://ubuntuforums.org/showthread.php?t=2004298