I have (had) 2 Jolla1, 1 Jolla C, the Jolla Tablet, A Xperia X, a F(x)tec Pro1, 2 Xperia 10 II and a rephone (all with SF on it). I never had issues with any of them regarding SSH. Before reflashing, are you sure that the phones are the culprit? Maybe there is a problem with your router.
I remember I had a similar problem and the only way to resolve it, was to copy .ssh folder from my backups, I didn’t spend much time to investigate further tho.
I can’t ssh to the phone from Linux laptop and also not from CLI of the Volla Phone.
But I can ssh to the phone from another fresh updated Xperia 10, that I never before used as a sftp client with my wife’s phone as server!
maybe a mess between old and new hostnames and certificates?
edit: I flashed the phone with 4.5.0.19, gave it a new host name and a new IP address, set up all connections, updated to 4.5.0.24, tested again → works now. Thank you all for the help!