Not able to authenticate using ssh keys

I have done this a lot of times before on github and bitbucket. But for some reason it’s currently not working. I followed all the steps here Use SSH keys to communicate with GitLab | GitLab

When I run this ssh -Tv git@git.mybayt.com

I get this

OpenSSH_8.2p1 Ubuntu-4ubuntu0.3, OpenSSL 1.1.1f  31 Mar 2020
debug1: Reading configuration data /home/gbarghouti/.ssh/config
debug1: /home/gbarghouti/.ssh/config line 1: Applying options for git.mybayt.com
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: include /etc/ssh/ssh_config.d/*.conf matched no files
debug1: /etc/ssh/ssh_config line 21: Applying options for *
debug1: Connecting to git.mybayt.com [132.145.229.118] port 22.
debug1: Connection established.
debug1: identity file /home/gbarghouti/.ssh/id_ed25519.pub type 3
debug1: identity file /home/gbarghouti/.ssh/id_ed25519.pub-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_8.2p1 Ubuntu-4ubuntu0.3
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.4
debug1: match: OpenSSH_7.4 pat OpenSSH_7.0*,OpenSSH_7.1*,OpenSSH_7.2*,OpenSSH_7.3*,OpenSSH_7.4*,OpenSSH_7.5*,OpenSSH_7.6*,OpenSSH_7.7* compat 0x04000002
debug1: Authenticating to git.mybayt.com:22 as 'git'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:tNq5mbAS9sPIgounr/Boo8j3Q4ntQuPqEReySd/9irQ
debug1: Host 'git.mybayt.com' is known and matches the ECDSA host key.
debug1: Found key in /home/gbarghouti/.ssh/known_hosts:11
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/gbarghouti/.ssh/id_ed25519.pub ED25519 SHA256:EDokzsfPekeg7//+OMTaZinuNgd3DpX1989ogQxmkvo explicit agent
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<rsa-sha2-256,rsa-sha2-512>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: publickey
debug1: Offering public key: /home/gbarghouti/.ssh/id_ed25519.pub ED25519 SHA256:EDokzsfPekeg7//+OMTaZinuNgd3DpX1989ogQxmkvo explicit agent
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: No more authentication methods to try.
git@git.mybayt.com: Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password).

It’s worth mentioning that our account is on a private domain and only accessible via VPN. Here is what I have in ~/.ssh/config

Host git.mybayt.com
  PreferredAuthentications publickey
  IdentityFile ~/.ssh/id_ed25519

And ls on ~/.ssh gives
config id_ed25519 id_ed25519.pub id_rsa id_rsa.pub known_hosts

So I have all the files available.
Appreciate any help or insight.