Solution 1 - Regenerate the key

1. Generate your key.
2. Configure ssh to use the key.Your config file should have something similar to the following:You can add IdentitiesOnly yes to ensure ssh uses the specified IdentityFile and no other keyfiles during authentication.

Setting IdentitiesOnly prevents failed authentications from occurring, when ssh would otherwise attempt to login with multiple keys.

Setting this is also considered more secure, as you're not leaking information about other keys you have installed, and maintaining separation of your keys between different levels of access.

1. Copy your key to your server.

Solution 2 - Perms

Sometimes the issue comes from permissions and ownership. For instance, if you want to log in as root, /root, .ssh and authorized_keys must belong to root. Otherwise, sshd won't be able to read them and therefore won't be able to tell if the user is authorized to log in.

In your home directory:

chown -R your_user:your_user .ssh

As for rights, go with 700 for .ssh and 600 for authorized_keys

chmod 700 .ssh
chmod 600 .ssh/authorized_keys

Solution 3 - SSHing into the home directory

Also make sure that the user's home directory (on the server) actually belongs to the user ssh'ing into (was set to root:root in my case).

Should have been:

sudo chown username:username /home/username;

Solution 4 - if you have access to both machines

The following method might work if you can access machineA and machineB independently (e.g. from machineC).

If ssh-copy-id is not working, password authentication could be disabled. The following is a workaround.

Having machineA's public key in machineB's authorized keys (i.e. ~/.ssh/authorized_keys) will allow you to ssh from machineA. This also applies to scp.

After generating the key pairs using: ssh-keygen

On machineA, execute cat ~/.ssh/id_rsa.pub

Sample output:

ssh-rsa AAAAB3NzaSGMFZW7yB anask@mahineA

Copy the printed key (⌘ Command+C, or CRTL+C) then add it to the ~/.ssh/authorized_keys file on machineB.

For example, execute the following on machineB:

echo 'ssh-rsa AAAAB3NzaSGMFZW7yB anask@mahineA' >> ~/.ssh/authorized_keys

Tailscale SSH Permission denied

In my case, my Tailscale key had expired. I needed to go into the Tailscale UI and stop it from expiring or create another key.