The guide you are providing is for virtual machines. If you are using a cloud image, it should have a preconfigured SSH key. What did you modify in your instance using that guide? Did you removed the previously included public keys in the
Are you specifying your previous SSH key when trying to connect vi SSH to your server?
Hope it helps,