I had this issue when setting up my ssh keys for Bitbucket on Fedora 34, even though my keys were fine.

ssh -T git@bitbucket.org

git@bitbucket.org: Permission denied (publickey).

Eventually I found this post on Stack Overflow which had the answer.

Add the following to your ~/.ssh/config file

Host bitbucket.org
 HostName bitbucket.org
 PubkeyAcceptedKeyTypes +ssh-rsa

Just like that:

ssh -T git@bitbucket.org

logged in as git

You can use git to connect to Bitbucket. Shell access is disabled