Fix GitHub SSH 'Permission denied (publickey)' after key rotation

Quick answer: Generate a new SSH key, add the public key to your GitHub account under Settings > SSH and GPG keys, then update the private key on your machine.

You rotated your SSH key — maybe because of a security policy, or you got a new laptop, or you lost your old key. Now when you run git push you see:

$ git push origin main
git@github.com: Permission denied (publickey).
fatal: Could not read from remote repository.

The problem isn't complicated. Your GitHub account still has your old public key stored. The new private key on your computer doesn't match that old public key. GitHub sees "unknown key" and says no.

Here's how you fix it step by step.

Step 1: Check what keys GitHub has for your account

First, log into GitHub in your browser. Click your profile picture in the top right, then Settings. On the left sidebar, click SSH and GPG keys. You'll see a list of SSH keys. Look for the one you think you rotated. If you see your old one, that's the issue.

After you check, don't delete anything yet. You'll add the new key first, then remove the old one.

Step 2: Generate a new SSH key (if you haven't already)

Open your terminal. Run this command:

ssh-keygen -t ed25519 -C "your_email@example.com"

Replace the email with the one you use on GitHub. Hit Enter. It'll ask where to save the key. Just press Enter to use the default location: ~/.ssh/id_ed25519. Then it'll ask for a passphrase. You can set one or leave it blank. Press Enter twice to skip it.

After it finishes, you should see something like:

Your identification has been saved in /home/you/.ssh/id_ed25519
Your public key has been saved in /home/you/.ssh/id_ed25519.pub

Step 3: Copy your new public key

Run this to print your new public key:

cat ~/.ssh/id_ed25519.pub

It'll output a long string starting with ssh-ed25519. Select and copy that entire line — including the ssh-ed25519 part and your email at the end. Don't miss any characters.

Step 4: Add the new public key to GitHub

Go back to the GitHub SSH keys page (Settings > SSH and GPG keys). Click the New SSH key button (green, near the top right). Fill in:

Title: Give it a name like "My laptop key 2025"
Key type: Leave as Authentication Key
Key: Paste your public key here

Click Add SSH key. GitHub might ask for your password. After that, you should see the new key in your list.

Step 5: Remove the old key (optional but recommended)

Find the old key in the list. Next to it, click the Delete button. Confirm. Now only your new key is associated with your account.

Step 6: Test the connection

Back in your terminal, run:

ssh -T git@github.com

You should see:

Hi username! You've successfully authenticated, but GitHub does not provide shell access.

If you see that, you're good. Try a push now:

git push origin main

What if it still says 'Permission denied'?

Check a few things:

Your SSH agent might not have loaded the key. Run ssh-add -l to see loaded keys. If yours isn't listed, run ssh-add ~/.ssh/id_ed25519
You might be using the wrong remote URL. Run git remote -v and make sure it's git@github.com:username/repo.git, not https://...
Your config file might be pointing to the wrong key. Check ~/.ssh/config for lines like IdentityFile. If it points to an old key path, update it to ~/.ssh/id_ed25519
Try a different key type. Rare, but some older systems don't support ed25519. Generate with ssh-keygen -t rsa -b 4096 instead and add that public key.

How to prevent this next time

Before you rotate your key, add the new one to GitHub while the old one still works. That way you never lose access. After you verify the new key works, then delete the old one. It takes two minutes and saves you from this exact problem.

Also, keep a backup of your .ssh folder before rotating keys. Copy it somewhere safe like a USB drive or password manager. If something goes wrong, you can always go back.

That's it. You should be pushing again in under five minutes.