Comment 36 for bug 94940

Ok, so I don't pretend to understand everything in this post. If you, like me, simply want to avoid delays logging in with ssh, stop avahi. For me, a simple "ssh server" took about 10 secs. Running with "ssh -o GSSAPIAuthentication=no server" brought that delay down to nothing. If that is also true for you:

Disable avahi on the client like this:
$ sudo /etc/init.d/avahi-daemon stop
Made it login without delay with or without GSSAPIAuthentication=no. Until the next reboot, where avahi will be restarted.
Disable avahi permanently by setting "AVAHI_DAEMON_START=1" in /etc/default/avahi-daemon worked for me. (Until I discover what avahi is and want to use it! :D)