Comment 43 for bug 84899

Yes, I agree with ed_p. Also for me, that is the problem.
For me, a simple "ssh server" took about 10 secs. Running with "ssh -o GSSAPIAuthentication=no server" brought that delay down to nothing. Disabling 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)