You change the MX records to point to the new provider. No downtime.

You also need to take care of SPF / DKIM / DMARC, but those records are for outbound mail.