Q: Will I lose purchased app when changing my iCloud id and user Id ?

You don't lose them. They will always be tied to the old Apple ID. You just won't be able to use them without repurchasing under the new Apple ID. Why not change the password on your email account?

Do not change apple IDs to a new ID. Change the email address for your ID.

Then you aren't using a strong enough password if you have been hacked unless the provider itself was hacked. If the provider was hacked then changing your Apple ID won't be of much use. The hacker is getting into the provider's data first, then yours second.

A new provider will help. But I agree with Ralph about changing the Apple ID because that will be a big hassle for you not to mention expensive.