It's because Ubuntu disabled RSA support. It's weird that SSH login works but Bolt doesn't, but re-enabling RSA actually fixed it. Here are the commands, in case anyone else runs into it in the near future:

# on Ubuntu 22.04 server
echo -e "HostKeyAlgorithms +ssh-rsa\nPubkeyAcceptedAlgorithms +ssh-rsa" >> /etc/ssh/sshd_config
/etc/init.d/sshd restart