This was a situation where right before leaving for the day, I saw the upgrade notice, clicked yes then left. Next morning, a bunch of my sync scripts started crashing and out of the first six servers I tried, only one let me in using password auth. I only had a bout an hour to (frantically) troubleshoot before I had to reinstall Monterey to be able to get work done. As I recall, Homebrew Started having weird dependency issues when I tried to use it. And frankly, I have a hard time with the cutesy terminology Homebrew likes to use.
I was using the stock SSH and rsync from Ventura. I modified my ssh config to force Diffie-Hellman and that at least gave me a connection. I don't think (but I'm not sure) that my SSH Keys had changed during the upgrade. I did not generate a new pair. But yes, the rsync scripts rely upon Key Authentication as in the link you posted.
You have given me some ideas. I only use Homebrew to add missing programs, I hadn't thought about seeing if i could replace the Mac SSH and rsync versions with ones from Homebrew.