How to change my Apple ID, if the previous one was compromised?

As stated elsewhere it is almost certainly a scam message.

As for the iCloud address, a primary address is not an alias. The first one you set up cannot be changed, but you can set up to 3 aliases which can be. Read: Add and manage email aliases for iCloud Mail on iCloud.com - Apple Support - "An email alias is an email address that conceals your actual email address from a recipient. An alias can help you manage the email you receive, and monitor the sources of unwanted messages. You can both send and receive email from an email alias using Mail on iCloud.com.

By the way, if you are using an iCloud address as your Apple ID that is a bad idea. Should you have problems logging into your account Apple will try to send you help emails to your Apple ID address, but if that's an iCloud address you won't be able to read them.

An address can't be "hacked" (people love over-using and misusing that term -- thank you Hollywood). Accounts can be compromised. That is more a matter of somebody knowing your password than your address. Frankly my "Apple ID" (= an email address) has been out on the web for decades. It's no big secret. But you need my password to get into my account. So somebody had your password too.

Your iCloud email address is a separate service Apple offers. As I may have said before, it is not a good idea to use your iCloud address for your Apple ID. Not so much for security reasons as because if you have problems with your account and Apple sends you emails to that account to help you, you won't be able to read those emails.

If you are having problems with spam (I don't use iCloud email at all and don't even have one set up) then look into setting up rules. Report and reduce spam in iCloud Mail - Apple Support

If you have gotten a email that is threatening to expose you this is not a compromised account, it is simply a scam message meant to scare you. Don;t be scared, delete the email, everything is okay

I'll add that with two factor authentication they would have also had to have had possession of your trusted devices and/or telephone numbers in order to get a verification code. Getting into an account is not easy.