Você reiniciou o ssh service? São dois logins SSH consecutivos (dentro de um minuto ou dois) ambos lentos?
Execute ssh -vvv user@host do cliente para ver onde ele aguarda.
Se isso não ajudar, você poderá interromper o serviço SSH (se tiver outras maneiras de acessar o host) e iniciar o SSH em primeiro plano com a depuração em: sshd -Dd . Em seguida, tente fazer uma conexão SSH e ver o que o servidor está fazendo.