For those receiving this error from Windows Server, I received this same error and it was a user account issue. With many organizations, group policy for Administrators may not allow setting up SSH Server and connections. With that type of setup, this must be done from Local Admin account. Might be worth looking into if you have confirmed there are not any typos in the public key.