Molto spesso è un problema di dns. Prova a impostare 'UseDNS no' in sshd_config.
Potrebbe essere un ritardo di ricerca DNS inverso. Se il tuo host di connessione non ha una voce DNS, prova ad aggiungere una voce per il tuo sistema di origine in /etc/hosts sul server a cui ti stai connettendo.