Server compromised with new password set?

My CentOS/cpanel server has been hacked. I know how to recover, but I would like some advice from all of you as to what you would do in this situation. The hack occurred in a strange way. I changed my root password last night around 8pm or so. I used a secure, 12 digit random password generated by lastpass. This was immediately after I had a company that I have used previously do some maintenance work on the underlying linux install (they were fixing an SFTP timeout issue). When they were done I changed the root pass to the new 12 character one. At 09:53 this morning the system sent an email saying someone from Palestine (37.8.xxxxx) had logged into the server using password authentication. -------- Time: Wed Aug 30 09:53:10 2017 -0500 IP: 37.8.xxxxxx(PS/Palestinian Territory/-) Account: root Method: password authentication --------------- However if I am reading the secure log correctly it says that that login failed but then they tried again with a different port. These port numbers shouldn't be accepting anything by the way. The port number I set in sshd_config is different. That is my first question. Why did ssh let them connect on a port other than the one I put in sshdconfig? ------------------ Aug 30 07:39:41 vps sshd[10925]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=37.8.xxxxx user=root Aug 30 07:39:42 vps sshd[10925]: Failed password for root from 37.8.xxxxx port 50937 ssh2 Aug 30 07:39:45 vps sshd[10925]: Connection closed by 37.8.xxxxx [preauth] Aug 30 09:53:10 vps sshd[29276]: Accepted password for root from 37.8.xxxxx port 64995 ssh2 ----------------------------- A few minutes later though at 09:58 I got an email saying that an old account was unsuspended. This is the email that made me notice the hack. The root login one went to my spam folder. Text below: ----------- This notice is the result of a request made by a computer with the IP address of "37.8.xxxxxx" through the "Unsuspend Account" service on the server while logged in as "root". The remote computer"s location appears to be: Palestine, State of (PS). The remote computer"s IP address is assigned to the provider: "Hadara Gaza BSA sub-route 2.1 - BSA-GAZA" The remote computer"s network link type appears to be: "generic tunnel or VPN". The remote computer"s operating system appears to be: "Windows" with version "NT kernel". The system generated this notice on 2017-08-30 at 14:58:35 UTC. ------------- At that point I immediately went through my VPS server panel and reset the root password to something stupidly long and random. There have been no more intrusions since then but the damage is done. I know they uploaded php crap to at least one account. The thing that boggles my mind is that the ONLY place that I put that password last night was in an email that I sent to myself. That, and it was also stored in my lastpass vault automatically. The email didn't have root in the subject or anything else that could tie it to my server. That makes me worried that my own computer at home might be infected or something. Either that or maybe somehow someone at the company that worked on the server last night did something? If you were in my situation what would you do? I can restore the individual accounts from off site backups but what would you do with the rest of the server? What do you think of the method they may have used to get the password? Would you wipe your local PC if this happened to you? Any insight from anyone who has been in this situation before? Thank you in advance.