The remote repository failed to update 5 minutes ago. Host key verification failed. fatal: Could not read from remote repository.

I am trying to Push to a remote repository, however, I keep getting the following message. I assume this is something todo with SSH Keys, however, I cannot figure it out. I have a Deploy key, set up which is link to my server. And yet it still doesn't work. I have a user set up on my linux server 'git' inside the users directory is a git repo 'repo.git'. I am trying to mirror my gitlab repo to my server repo. However it keeps failing. Do I have to set up a Private key on Gitlab some how?

The remote repository failed to update 5 minutes ago.
Host key verification failed.
fatal: Could not read from remote repository.

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