I have searched this issue and followed many instructions on how to connect to gitlab via SSH from RHEL8 client. None of the common resolutions / configurations are working to solve this connection issue in my case and I am at a loss as to what could be wrong. In all cases, the test ssh connection fails with permission denied (publickey,password).

What is interesting is that /var/log/secure never shows a connection attempt on the server, I checked log config to ensure this is the correct log location.

Steps Taken:

SSH Key Configuration:
    Generated a new ED25519 SSH key pair.
    Added the public key to GitLab under the user's SSH keys.
    Manually copied the public key to /home/git/.ssh/authorized_keys on gitlab server.
    Verified correct permissions and ownership for /home/git/.ssh and authorized_keys.

SSH Service and System Configuration:
    Edited sshd_config to allow password authentication and public key authentication:

    PubkeyAuthentication yes
    PubkeyAcceptedKeyTypes +ssh-ed25519,ssh-rsa,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521
    AuthorizedKeysFile      .ssh/authorized_keys

Permissions:

Ensured correct permissions and ownership for the .ssh directory and authorized_keys file:

Server:
sudo chown -R git:git /home/git/.ssh
sudo chmod 700 /home/git/.ssh
sudo chmod 600 /home/git/.ssh/authorized_keys

Client:
chmod 600 ~/.ssh/new_gitlab_key
chmod 644 ~/.ssh/new_gitlab_key.pub

Connection Attempt:

Attempted to connect using the SSH key with detailed debug output:

ssh -i ~/.ssh/new_gitlab_key -o IdentitiesOnly=yes -vvv git@gitlab.{{domain}}.com

Encountered "Permission denied (publickey,password)" error.

Client SSH Configuration:

Edited ~/.ssh/config file on the client to specify settings for connecting to GitLab:

Host {{username}}.gitlab.{{domain}}.com
  Hostname gitlab.{{domain}}.com
  User git
  IdentityFile ~/.ssh/new_gitlab_key
  PreferredAuthentications publickey