Can't clone a gitlab repo with SSH

I've generated public/private key pair with ssh-keygen :

ssh-keygen -t ed25519 -C "git@gitlab.xxx"

I've added the contents of the public key with .pub extension in the "deploy keys" section of gitlab repo and ensured it was "enabled".

I've also added it to my account settings under "SSH keys".

When I try to clone the repo with a ssh git clone :

git clone git@gitlab.xxx:path/to/repo.git

It still requests a password and when I input the passphrase it says "Permission denied". I also tried without passphrase after re-generating a key without passphrase.

Same thing when I try to specify a key :

git clone git@gitlab.xxx:path/to/repo.git --config core.sshCommand="ssh -i /path/to/private_key"

with ssh -vvv git@gitlab.xxx -i /path/to/private_key it says :

debug1: Offering ED25519 public key: /path/to/private_key"
debug3: send_pubkey_test
debug3: send packet: type 50
debug2: we sent a publickey packet, wait for reply
debug3: receive packet: type 51
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug2: we did not send a packet, disable method
debug3: authmethod_lookup password
debug3: remaining preferred: ,password
debug3: authmethod_is_enabled password debug1: Next authentication method: password

There were several issues with the Gitlab server:

1. It didn't support ed25519, it supported only rsa
2. It refused git as a user, it expected some service account name instead

git clone svcaccnt@gitlab.xxx:path/to/repo.git --config core.sshCommand="ssh -i /path/to/private_key"