OK - the issue was the firewall rules that we had.

Nice!

But now there is an issue with the

Setting up connection to remote session

OutrageousSheep60 this is just a warning, basically saying we are using the default signed SSH server key (has nothing to do with the random password, just the identifying key being used for the remote ssh session)
Bottom line, I think you have everything working 🙂