I highly recommend reading the two links that EEAA commented, along with a third:
Essentially you have the right idea. Specify your additional nameservers as NS records in both of your zones (Route 53 and Cloudflare), and then add those new nameservers to your registrars configuration for your domain.
There will be zero downtime if you do this correctly.
The way to ensure you do this correctly is to use a tool like Stack Exchange's DNS Control to make the changes for you. Get it working with your current single DNS provider, and then just throw in the config to tell DNS Control to send the zone to multiple providers.
Note: I just saw in the comments that you are using orange-cloud with CloudFlare. An orange-cloud setup is totally incompatible with 3rd party DNS providers, as CloudFlare manipulates your served DNS records. This will only work for grey-cloud sites.
Don't let that put you off DNS Control though, as DNS Control has support for orange cloud control (just don't use dual DNS providers with orange cloud)