I've only ever seen this in Ubuntu for some reason and it is because of the /etc/nsswitch.conf settings. So the issue is that if the hostname's reverse DNS cannot be found that you need to go back to DNS which was not the default in this nsswitch.conf file for some strange reason. Edit /etc/nsswitch.conf and replace your "hosts" line with this: #hosts: files dns mdns4_minimal [NOTFOUND=return] mdns........

Icouldn't understand why on one system it took a few minutes to get the SSHlogin prompt when connecting to other systems. The other systems all had the UseDNS parameter set to no, which almost always resolves the login prompt delay. The reason is Ubuntu and perhaps Debian and other distributions /etc/nsswitch.conf file Edit yours to have the "hosts" line like so (notice that files and dns are the primary resolution choice........