VCS labeling github failed - push not permitted

We're using the VCS labeling Build Feature to push label tags to GitHub.

It was working fine for us for quite some time, but stopped working within the past 6 months with this error:

Failed: Failed to set label '7.0.20190304-330s': Labeling failed: org.eclipse.jgit.errors.TransportException: git@github.com:[redacted]/[redacted].git: push not permitted

We are using TeamCity Professional 2019.1.1 (build 66192)

Our VCS root is configured with just the Fetch URL in the `git@github.com:[redacted]/[redacted].git` format. We're using "Uploaded Key" authentication method.

I did see a few older posts related to VCS labeling fails, recommending to define a Push URL with http(s). We haven't tried that yet, just wasn't sure how that would jive with 'Uploaded Key' authentication method.

Any help would be greatly appreciated. Thanks!