We have two compute engine instances(both Linux VM's) on one Project. One I had access through Putty and it was connecting fine. But the other instance I had the "Server Refused our Key" error when trying to connect through putty. In trying to fix the issue with the one giving the error, I removed all ssh keys in the Metadata and used a new key on the Compute engine and now I'm having the issue on both instances. These are our production servers so we need the access. Other than changing out the SSH Keys, I haven't tried much else. I'm limited in Knowledge.
I read the answer on other issues here, but none described the solution well enough for me to follow.
I was able to gain access to the VM instance by going to the Compute Engine in the Project and using the SSH web browser console. Once connected and in the server, I made sure I was in my home directory by typing "pwd". Then I navigated to "cd /.ssh". There is a file there called, "authorized_keys". To edit the file I used a text editor called ee(easy editor), I used "ee authorized_keys" to open the file. Using Putty Keygen, I load my private key to see the text I need to copy. I moved my cursor to the end of page and pasted the Open ssh text from my Key to the authorized-keys file. To exit the easy editor press Escape key, a menu will pop up and you need to select "leave editor". You will be then asked to save changes. After I did these steps I was able to get into the VM instance using putty.