I just ran into this issue when sshing to a server with GSSAPIAuthentication enabled. Even though I am not using GSSAPI auth, Debian's default on the client side added 15s to the login time. I agree with other folks that GSSAPI auth is unusual and should be disabled by default since it may cause significant delays.
# With GSSAPIAuthentication on $ time ssh -v foo hostname <snip> debug1: Next authentication method: gssapi-with-mic debug1: No credentials were supplied, or the credentials were unavailable or inaccessible No Kerberos credentials available (default cache: FILE:/tmp/krb5cc_1000) debug1: No credentials were supplied, or the credentials were unavailable or inaccessible No Kerberos credentials available (default cache: FILE:/tmp/krb5cc_1000) <snip> real 0m15.204s user 0m0.010s sys 0m0.011s # With GSSAPIAuthentication off $ time ssh -v foo hostname real 0m0.195s user 0m0.014s sys 0m0.007s
