If you check out the travis-ci status page (http://www.traviscistatus.com/) you’ll notice that the “Active Linux Builds for Open Source projects” periodically maxes out. Based on how the travis private build system works (a single queue for all “Build Jobs” with no more than x running at a time), I suspect they have a single queue for all open source Build Jobs.
You can split up your build in to multiple jobs, each of which would finish faster. When Travis is under light use they would run in parallel and your build will return sooner, but when Travis is running lots of other builds yours may only run sequentially.
Looking at the .travis.yml in the repo you posted, you may notice good performance increases by adding apt and pip caching (http://docs.travis-ci.com/user/caching/). You should also consider switching to Travis’ new container-based infrastructure (http://docs.travis-ci.com/user/workers/container-based-infrastructure/). That will only work however if you’re able to replace the sudo apt-get commands in your build.