[LightDestory]

When changing SSH port I always perform these actions:

1. First allow traffic on the interested port and make sure to reload/restart the firewall service
   
2. Edit sshd.conf replacing port 22 with the interested port and make sure to restart sshd service
   
3. (It is possible that a reboot is required: only once happened to me)
   

Do you do these action too?
Currently we don't know the exact issue because the "lost SSH access" can be due to:

• Closed port
  
• sshd service not running
  
• Unmatching host-keys betweeb device and server.
  

The last one can be fixed deleting your ".known-hosts" file placed inside the ".ssh" folder.

You said that your IP has been changed, did you try to flush your DNS records? Did you try SSH into VPS using the IP address directly?