When my first ssh connection to a new server had a 30secs delay, I thought I was cool enough to speed it up with
#ssh -o GSSAPIAuthentication=off
but this time it didn’t work.

I didn’t waste time and simply strace and connected
#strace -qfp $(pgrep -f /sshd)
...
[pid 15756] socket(PF_INET, SOCK_DGRAM|SOCK_NONBLOCK, IPPROTO_IP) = 7
[pid 15756] connect(7, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("10.0.0.254")}, 16) = 0
...
[pid 15756] poll([{fd=7, events=POLLIN}], 1, 5000) = 0 (Timeout)
....


That was something involving DNS and ssh…
# grep -ri dns /etc/ssh/
...
/etc/ssh/sshd_config:#UseDNS no


So you may consider to disable it, as it’s enabled by default.

A 30 second delay should have been considered a DNS issue even without strace, but nobody is perfect and that way worked fine ;)