Consegui recuperar o acesso ssh novamente. Por alguma razão, a regra ufw para a porta 22 foi perdida. Deveria ter sido o primeiro lugar para procurar, mas foi um erro da minha parte não questionar se o serviço ssh estava funcionando. Eu fiz uma má suposição de que estava em baixo. Lição aprendida.
Se um iniciante com o mesmo problema tropeçar nisso, se você usar o ufw, verifique seu /lib/ufw/user.rules e /lib/ufw/user6.rules para ver se existe uma regra para o OpenSSH. No meu caso adicionando o abaixo resolveu:
### tuple ### allow any 22 0.0.0.0/0 any 0.0.0.0/0 in
-A ufw-user-input -p tcp --dport 22 -j ACCEPT
-A ufw-user-input -p udp --dport 22 -j ACCEPT