Git refuses to push with "Permission denied (publickey)" and my key is definitely on the server

The causes, in the order I check them:

Wrong key offered, or none. Fix in ~/.ssh/config:

Host your-host
    User git
    IdentityFile ~/.ssh/id_ed25519
    IdentitiesOnly yes

IdentitiesOnly yes matters more than people expect. Without it the client offers every key it has, and some servers cut you off after a handful of failures before reaching the right one.

Permissions too open. The client silently refuses to use a private key that others can read. chmod 600 on the key, 700 on ~/.ssh. This produces exactly your symptom and no useful message unless you run with -v.

The wrong half pasted. The registered key must be the contents of the .pub file, one line, starting with the algorithm name. Pasting the private half is common and the site usually accepts it without complaint.

The agent is not running, or the key was never added to it. ssh-add -l tells you in one line.

Stop guessing and ask the client what it is doing. This one command answers it almost every time:

ssh -vT git@your-host

Read the output for two things.

Which keys it offered. You will see lines like Offering public key: /home/you/.ssh/id_ed25519. If the key you registered is not in that list, the server never saw it — the problem is local, not on the server. That is the single most common cause and people spend hours on the account page instead.

What the server said. A successful attempt ends with a message naming your account. If it offers keys and gets refused, the key it offered is not the one registered.

The reason the right key often is not offered: the client tries a small set of default filenames and then gives up. A key named anything else is invisible unless you tell it, and the fix is a config entry rather than a new key.

Two more that produce the identical message and are not about your key at all.

You are authenticating as the wrong user. The remote URL for these services is almost always git@host:group/repo.git. If yours has your own username in front, the server is looking for a key belonging to a user that does not exist.

An older key type is no longer accepted. Servers and clients have both been retiring older algorithms, and a key generated years ago can stop working after an upgrade at either end with no warning. If -v shows the key being offered and refused, generating a modern one and registering it takes two minutes and rules this out.

Generate with ssh-keygen -t ed25519 unless you have a specific reason to want something else.