Hi @Michael Drapkin,
Good catch! Glad the issue is resolved for you finally. I will have this answer promoted by reposting it. As an Original Poster(You) will not be able to accept your own answer. This is in the attempt to help others looking for a solution for a similar issue.
The group permissions were linked to the private key file, which was preventing SSH from working. By removing it, it was able to connect to new Azure VPS and continue working.
Thanks again for sharing the solution here. Have a good day!