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.
It works. Thanks!
It works for ubuntu 10.10 as well! Thank you!!
Good stuff! This DNS trick fixed it up for me.
Thanks!
Thanks, setting “UseDNS no“ works on my Ubuntu Server 10.04.
Fred Mora’s tip about GSS config did the trick for me on Ubuntu 11.10, thanks!