Isso parece um problema de rede.
Indague se algum equipamento de rede foi alterado ou foi reconfigurado. Diga ao seu administrador de rede que você está tendo problemas com o ssh, pode haver um erro de configuração em um firewall. Tente fazer login em outras máquinas ou em outras máquinas para melhorar o diagnóstico.
Uma causa possível desses sintomas é um conflito de endereço IP. Verifique onde o cliente e o servidor estão obtendo seu endereço IP. Se você mantiver ping server.example.com em execução, ajudará a tornar a conexão mais longa? Em caso afirmativo, você tem um conflito de endereço IP. (O ping ajuda porque continua dizendo aos roteadores ao longo do caminho para rotear os pacotes IP para sua máquina - mas você ainda perderá a conexão se a outra máquina enviar uma resposta ARP antes de você.) Se esse é o problema, você precisa consertá-lo: organize uma das máquinas que estão usando o mesmo endereço para usar um endereço diferente.
Verifique também a tabela de roteamento na sua máquina. Certifique-se de que os pacotes para o servidor sejam roteados para a interface apropriada. (Embora uma tabela de roteamento incorreta normalmente faça a conexão não funcionar, existe um caso extremo onde os sintomas são aqueles que você descreve: se você obtiver um endereço com DHCP e o servidor DHCP também for o servidor que você está contatando - o endereço do servidor DHCP será roteado para a interface desejada até que o seu cache ARP expire.)