Is this a reasonable assumption?
Usar duas rotas diferentes elimina o atacante perto de você na rota, o que lhe dá alguma pista, mas não garante que não haja um invasor em algum lugar próximo ao servidor .
Geralmente esse aviso é por causa das chaves realmente alteradas, mas você não pode ter certeza. A maneira mais fácil é verificar com o administrador do servidor. De preferência, ele deve publicar a impressão digital da chave por algum outro canal confiável (página https, registro DNS SSHFP).