C'est le plus souvent un problème de DNS. Essayez de définir 'UseDNS no' dans sshd_config.
Il pourrait éventuellement s'agir d'un délai de recherche DNS inversé. Si votre hôte de connexion n'a pas d'entrée DNS, essayez d'ajouter une entrée pour votre système source dans /etc/hosts sur le serveur auquel vous vous connectez.