Eu tive um problema semelhante e, eventualmente, acabou sendo devido ao tráfego do meu provedor de serviços de Internet (ou de alguma forma mexer com) em portas não padrão. Eles aparentemente acham que qualquer coisa que não esteja nas portas 25/80/443 etc é o compartilhamento de arquivos e intencionalmente o atrasa.
Eu sugiro que você tente mudar de provedor, ou primeiramente você também pode tentar configurar o sshd para escutar na porta 443 (assumindo que você não tem um servidor web com SSL naquela máquina) e tente desta forma.