Solution 1:

I think it is more probably a DNS issue than GSSAPI. sshd likes prompt DNS responses to work promptly during connection phase... cause of logging and access checks.