Sua teoria é basicamente correta, pois o seu problema é causado por dyndns. Mais precisamente, o seu problema é causado por ter um endereço IP dinâmico; O dyndns torna as coisas mais fáceis, mas não completamente perfeitas.
Quando o seu roteador recebe um novo endereço IP dinâmico (porque foi reinicializado ou porque seu provedor o desconectou por algum motivo¹) [etapa 1, etapa 4], é necessário efetuar login no novo IP. Quando o seu roteador se conecta, ele envia uma mensagem ao seu provedor dyndns notificando-o da alteração do endereço. Quando você executa ssh johnny8888.dyndns.example.com , o cliente ssh procura o endereço IP correspondente a johnny8888.dyndns.example.com .
As informações do DNS levam algum tempo para serem propagadas, porque são armazenadas em cache. Para uso típico de dyndns, o atraso é de alguns minutos. Portanto, se você tentar se conectar logo após a alteração de um endereço IP, ainda poderá alcançar o endereço IP antigo [etapa 3], que agora é atribuído a uma máquina diferente. Se esta máquina executar um servidor ssh, você obtém o aviso de alteração da identificação do host remoto.
Adicione CheckHostIP No ao seu ~/.ssh/config , na seção do seu roteador. Então o ssh não irá verificar a chave associada ao seu endereço IP (que é inútil já que você tem um endereço dinâmico), somente a chave associada ao seu nome de host (que não irá mudar).
Observe que na maioria das vezes, você não obterá o aviso de alteração de identificação do host remoto. Você só obtém se tentar entrar na máquina de outra pessoa, ou tentou no passado. (Suas tentativas seriam acidentais, quando você tiver tido azar de tentar se conectar depois de uma alteração no endereço IP e antes da atualização do DNS ter se propagado.)
Muitos ISPs desconectam cada cliente todos os dias ou a cada poucos dias, porque isso facilita o balanceamento de carga. Você pode se reconectar instantaneamente, mas pode obter um endereço IP diferente.