As of Ubuntu 8.10 and older, connections to SSH servers with default configs can be annoyingly slow. This
is because the OpenSSH daemon uses DNS to run a reverse lookup on the client to be sure that they aren’t faking their hostname. You can disable most look-ups by implementing the following setting:
As root edit “/etc/ssh/sshd_config” and add the line “UseDNS no“.
This can also be done by running the following command:
sudo echo "UseDNS no" >> /etc/ssh/sshd_config
Sources:
This issue is documented at OpenSSH.org
Fix and more details available at: http://tech.waltco.biz/2008/02/02/ssh-slow-to-connect-in-ubuntu-710-gutsy-gibbon/


Thanx, your saved post saved me some hours of trying to find the reason myself.
On Ubuntu 10.04 (Lucid Lynx), I had a similar problem. I found out that the /etc/ssh/ssh_config (config file for the ssh client) was overriding the defaults with
GSSAPIAuthentication yes
GSSAPIDelegateCredentials no
I commented out these two lines. Now ssh is not waiting for GSS anymore and the login speed is back to normal.