Look into using Travis build stages

https://docs.travis-ci.com/user/build-stages/

And we should definitely try and fix #23387 (closed) too...

/CC @Johann-S