O cliente parece estar chamando a verificação de DNS, portanto
UseDNS no
GSSAPIAuthentication no
no servidor são inúteis.
A verificação de DNS no cliente foi introduzida (aparentemente) com um patch GSSAPI introduzido para compatibilidade com o SunSSH:
Adicionando
GSSAPIKeyExchange no
para ssh_config (não sshd_config) resolveu o problema.
Veja também: link