Found my answer, leaving it here for posterity.

Issue seems to be that there are multiple ssh configs now, and not only /etc/ssh/sshd_config. In my case (ubuntu 22.04) there was a sneaky file /etc/ssh/sshd_config.d/60-cloudimg-settings.conf that had a single line PasswordAuthentication no that was WREAKING MY LIFE!!!!

Fixed it with this:

grep -r PasswordAuthentication /etc/ssh -l | xargs -n 1 sed -i 's/#\s*PasswordAuthentication\s.*$/PasswordAuthentication yes/; s/^PasswordAuthentication\s*no$/PasswordAuthentication yes/'

Also, service ssh restart was not working and needed to use systemctl restart ssh.service instead.

Found my answer, leaving it here for posterity.

Issue seems to be that there are multiple ssh configs now, and not only /etc/ssh/sshd_config. In my case (ubuntu 22.04) there was a sneaky file /etc/ssh/sshd_config.d/60-cloudimg-settings.conf that had a single line PasswordAuthentication no that was WREAKING MY LIFE!!!!

Fixed it with this:

grep -r PasswordAuthentication /etc/ssh -l | xargs -n 1 sed -i 's/#\s*PasswordAuthentication\s.*$/PasswordAuthentication yes/; s/^PasswordAuthentication\s*no$/PasswordAuthentication yes/'

Also, service ssh restart was not working, no error, just didn't do anything and needed to use systemctl restart ssh.service instead.