Isso definitivamente não é normal. Tendo em conta os seus sintomas, acho que você está enfrentando um conflito de endereços IP. Existem duas máquinas na sua rede com o mesmo endereço IP, e uma delas é o servidor que você está tentando acessar. Às vezes você está alcançando a máquina esperada e tudo está bem. Às vezes, você acessa outra máquina que tem uma chave SSH diferente e sua conexão é rejeitada.
Quando há um conflito de endereços IP, é comum que um roteador bloqueie na rota para um endereço IP até que um cache expire, então consulta a rota novamente e atualiza para corresponder quem responde primeiro, produzindo resultados aleatórios. Não há nada que impeça a alternância acontecer no meio de uma conexão TCP.
Roteadores sofisticados geram um alerta quando ocorrem conflitos de IP, portanto, o administrador da rede já pode estar rastreando isso. Se você estiver root no seu servidor, você pode resolvê-lo escolhendo um endereço IP não atribuído. Se você está obtendo o seu endereço IP através do DHCP, entre em contato com o administrador do DHCP.