There is a feature of OpenSSH, enabled by default, that causes the ssh daemon to do a name lookup for the client and confirm that it matches its IP address. This is supposed to check against some sort of IP spoof during SSH login attacks. However on my local network which lacks a DNS, it results in lengthy delays during logins.

I found good explanations and how to fix this in the OpenSSH FAQ and also on the SUSE Linux Forums and a couple of blogs. This issue also comes up as at least one bug for Ubuntu (but it's not a bug, it's a feature).

In a nutshell: if you want to remove this delay and don't care about doing reverse lookups, set UseDNS no in /etc/ssh/sshd_config and then restart the daemon. The FAQ explains it better than me.