How can I push to protected github branches with a deploy key

We have github enterprise set up at work and I want a travis build to push code back to the repo as part of the master branch build. It basically updates the changelog, commits the file and need to push back to the repo. The problem is that we have protected branches, and trying to push with the deploy key set up with travis yields:

remote: error: Required status check "continuous-integration/travis-ci" is expected.
At least one approved review is required.        
! [remote rejected]   master -> master (protected branch hook declined)

It doesn't help that the protected branch is set up to allow admins to override, becuase the deploy key is not regarded as an admin AFAIU.

Now in 2021 the documentation says that "[d]eploy keys with write access can perform the same actions as an organization member with admin access". If you disable the Include administrators restriction, the deploy key can be used to push to the protected branch.