você provavelmente tem a chave no arquivo .ssh / knownhosts em sua máquina local.
vim .ssh / knownhosts em seguida, localize esse endereço IP (do servidor), remova essa chave, salve e saia e tente ssh novamente.
o problema é que sua chave do host conhecido pode estar ligando você ao usuário original, agora o novo .....