I couldn't understand why on one system it took a few minutes to get the SSH login 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)

hosts:          files dns mdns4_minimal [NOTFOUND=return] dns mdns4

If the above does not work - disable GSSAPI auth

This permanently caused my slow SSH login problems:

Edit vi /etc/ssh/ssh_config

Disable GSSAPI auth by setting the following line (make sure to uncomment or change the existing line if there is one that says yes):

GSSAPIAuthentication no

I realized what has happening by running -v with SSH, it kept timing out and trying to use GSSAPIAuthentication before trying password, unlike some older systems I have.

I'm sure this is a real annoyance for a lot of people too.