SSH - Permission denied (publickey)

Before I get into this, I just wanted to say that I've read many posts about this problem and none of them were helpful. I tried changing the permissions and it didn't work.

Permission of ~/.ssh folder must be 700, ~/.ssh/id_rsa : 600, ~/.ssh/id_rsa.pub : 644

I've got two Ubuntu 20.04 machines, a desktop and a laptop. Using password based authentication, I was able to copy both public keys to the other computer using ssh-copy-id -i ~/.ssh/id_rsa.pub [email protected]. I then changed the following lines in /etc/ssh/sshd_config on both machines:

PubkeyAuthentication yes
PasswordAuthentication no

When I attempted to connect via ssh using public key from the desktop to the laptop, it worked fine. However, when I tried the opposite, laptop to desktop via public key, I got Permission denied (publickey). When I switch back from Public Key Authentication to Password authentication, it works. I wanted to post the ssh -vvv output but askubuntu marked it as spam.

Thank you.