Host key verification failed

Olá,

Eu fiz uma troca de usuário administrador do meu PC e isso acabou removendo meus dados do Git. Como meus projetos ficam numa outra partição, as suas características permaneram as mesmas.

Eu acrescentei uma nova SSH Key no GitLab e configurei o usuário e o e-mail. Mas ao tentar dar o push para o remoto recebo o seguinte erro:

Host key verification failed.

fatal: Could not read from remote repository.

Please make sure you have the correct access rights and the repository exists.

O que posso fazer para solucionar este caso?