ssh connection slow when using @hostname.com, but not when using @ipaddress

You'll need to add

GSSAPIAuthentication no

...to /etc/ssh/ssh_config, not /etc/ssh/sshd_config as you've said. To check if that's definitely the fix, try adding -o GSSAPIAuthentication=no to your commandline to see if that changes things.

I am using a Mac client. Disabling GSSAPIAuthentication on the server had no effect.

I followed http://hints.macworld.com/article.php?story=20111020115417965 and turned off IPv6 in my ~/.ssh/config by adding:

Host ...
AddressFamily inet

This solved the issue :-)

You may have some DNS problems on the client side, check how much time it needs to resolve your server's hostname:

[vitalie@silver ~]$ time host www.google.com
www.google.com is an alias for www.l.google.com.
www.l.google.com has address 74.125.87.99
www.l.google.com has address 74.125.87.104

real    0m0.727s
user    0m0.002s
sys     0m0.008s