Why does GitLab server return "Next Authentication method: password" and not use key?

Question

Admins at my company are at a loss. I am trying to connect to my company's gitlab instance using the following but even this password is denied:

ssh -Tv git@host.company.com

My pub/priv keys are in ~/.ssh and I've added the key to the GitLab account. I get these results:

debug1: Connecting to host.company.com [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: identity file /home/me/.ssh/id_rsa type 0
debug1: identity file /home/me/.ssh/id_rsa-cert type -1
debug1: identity file /home/me/.ssh/id_dsa type -1
debug1: identity file /home/me/.ssh/id_dsa-cert type -1
debug1: identity file /home/me/.ssh/id_ecdsa type -1
debug1: identity file /home/me/.ssh/id_ecdsa-cert type -1
debug1: identity file /home/me/.ssh/id_ecdsa_sk type -1
debug1: identity file /home/me/.ssh/id_ecdsa_sk-cert type -1
debug1: identity file /home/me/.ssh/id_ed25519 type 3
debug1: identity file /home/me/.ssh/id_ed25519-cert type -1
debug1: identity file /home/me/.ssh/id_ed25519_sk type -1
debug1: identity file /home/me/.ssh/id_ed25519_sk-cert type -1
debug1: identity file /home/me/.ssh/id_xmss type -1
debug1: identity file /home/me/.ssh/id_xmss-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.2p1 Ubuntu-4ubuntu0.4
debug1: Remote protocol version 2.0, remote software version OpenSSH_8.2p1 Ubuntu-4ubuntu0.3
debug1: match: OpenSSH_8.2p1 Ubuntu-4ubuntu0.2 pat OpenSSH* compat 0x03000000
debug1: Authenticating to host.company.com:22 as 'git'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
...
debug1: Host 'host.company.com' is known and matches the ECDSA host key.
debug1: Found key in /home/emp/.ssh/known_hosts:1
debug1: rekey out after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey in after 134217728 blocks
debug1: Will attempt key: /home/me/.ssh/id_ed25519 ED25519SHA256:ABCDEFGHIJKLMNOPQRSTUVWXYZ agent
debug1: Will attempt key: /home/me/.ssh/id_rsa RSA SHA256:ABCDEFGHIJKLMNOPQRSTUVWXYZ agent
debug1: Will attempt key: /home/me/.ssh/id_dsa 
debug1: Will attempt key: /home/me/.ssh/id_ecdsa 
debug1: Will attempt key: /home/me/.ssh/id_ecdsa_sk 
debug1: Will attempt key: /home/me/.ssh/id_ed25519_sk 
debug1: Will attempt key: /home/me/.ssh/id_xmss 
debug1: SSH2_MSG_EXT_INFO received
...
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /home/me/.ssh/id_ed25519 ED25519 SHA256:ABCDEFGHIJKLMNOPQRSTUVWXYZ agent
debug1: Authentications that can continue: publickey,password
debug1: Offering public key: /home/me/.ssh/id_rsa RSA SHA256:ABCDEFGHIJKLMNOPQRSTUVWXYZ agent
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /home/me/.ssh/id_dsa
debug1: Trying private key: /home/me/.ssh/id_ecdsa
debug1: Trying private key: /home/me/.ssh/id_ecdsa_sk
debug1: Trying private key: /home/me/.ssh/id_ed25519_sk
debug1: Trying private key: /home/me/.ssh/id_xmss
debug1: Next authentication method: password
git@host.company.com's password: 

It always ends up asking for the password. Same results if I use my username in this.

ssh -Tv me@host.company.com

Anyone have thoughts?

Answer 1

First, I confirm me@host.company.com will never work: 'me' does not have a homedir on that server.
The public key you must register on your GitLab server is managed by the service account git.

Try for testing a key with the old PEM format, just in case:

ssh-keygen -t ed25519 -P "" -m PEM -f ~/.ssh/mygitlab
ssh -Tv -i ~/.ssh/mygitlab git@host.company.com