Error Permission denied (publickey) when I try to ssh

Recently I threw out my old linux laptop and set everything up again in my new laptop. The only trouble I have now is not being able to log in to my DO instance via ssh. This instance had one ssh key setup before and in the sshd config it had permitrootlogin set to no. So I created a new ssh key to be able to login from this new laptop.

$ ssh-keygen -t rsa -C "gitlab" -b 4096

Then added the public key this to the instance. Now I try to login

$ ssh user@server

I get asked password for this user. I am able to login using the password. This isn’t how I was logging in before. I used to type my ssh passphrase. So I thought this may be because this is a new key and I disabled password authentication in sshd config. After this, I get the error

$ ssh user@server
Permission denied (publickey)

I checked online and set the permission to .ssh folder to 700. Still I get the same error. I can access the online console of the instance, but don’t know what to do.

How do I resolve this?