If you are having issues with GitLab deploy keys make sure you are exporting them in the right format.

I first created my keys with this incantation:

ssh-keygen -t rsa -b 4096  -C "your@email.com" -f ./ops/keys/id_rsa

This will generate a key that starts with the following header:

>-----BEGIN OPENSSH PRIVATE KEY-----

When in fact you need RSA keys. Try adding the -m pem flag:

ssh-keygen -t rsa -b 4096 -m pem  -C "your@email.com" -f ./ops/keys/id_rsa

That will generate a header like:

>-----BEGIN RSA PRIVATE KEY-----