Since you planned ahead, it should be as simple as getting a new provider and updating the MX record. If you are looking for suggestions, I'm on Fastmail's $50/year plan and quite happy with it.

https://www.fastmail.com/how-to/email-for-your-domain/