Passing the ssh key type to the ssh-keyscan command using -t ecdsa solved the problem for us!! 
Gitlab is using OpenSSH as the ssh client and as it turns out OpenSSH prefers ECDSA key type if the server provides it and Gitlab server does provide this type of key along with other types. If you don’t pass the key type, all the available keys are fetched from Gitlab and written to your known_hosts file. However, I noticed that in the process of fetching these keys and writing them to the ~/.ssh/known_hosts file, sometimes the ECDSA key comes after the RSA key, and that causes the verification failure. So just kill the noise and fetch the key that the client is looking for. Long story short, here is the command that should do it for you:
for ip in $(dig @8.8.8.8 gitlab.com +short); do ssh-keyscan -t ecdsa gitlab.com,$ip; done 2>/dev/null >> ~/.ssh/known_hosts