A principal causa desse tipo de atraso no ssh é a resolução de DNS do cliente. No servidor ssh, você não pode fazer uma pesquisa inversa do endereço IP da máquina cliente Windows? A mesma pesquisa funciona para os clientes Linux?
Se for esse o caso, adicione a seguinte linha ao /etc/ssh/sshd_config
do servidor para desativar a pesquisa de DNS do endereço IP:
UseDNS no
Você também pode dar uma olhada na entrada do FAQ do OpenSSH para esse tipo de problema: link