Why do I get this APT warning: Signature by key [...] uses weak digest algorithm (SHA1)?

I'm hosting a private Debian repository for some custom Raspberry Pi code. I originally built the software on Raspbian Jessie (version 8), generated a GPG key which I use to sign the repository, and ran sudo apt-key add ... on all the devices, to ensure that they would be able to authenticate my repository. This worked fine, until lately I add some new devices running Raspbian Stretch (version 9). Even though I added the exact same GPG key to them, here is the output I see when I run sudo apt-get update:

W: GPG error: http://url.of.private.repo stable Release: The following signatures were invalid: 95F9B44CE35F40B759D59C2A77E4184C595493B1
W: The repository 'http://url.of.private.repo stable Release' is not signed.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.

However, this only happens on the newer boxes. On the Pis that are still running Jessie, I can run sudo apt-get update all I want and it does not give me any authentication warnings.

Why is that the Pis running Stretch think the GPG key is invalid, even though they're all sharing the same key? I could generate a new key on a box running Stretch, but I am hoping to avoid adding new GPG keys to every single Jessie box. (Right now I have only a handful of the new boxes running Stretch, whereas ~200 of the boxes are still running Jessie.) What can I do to convince the Stretch boxes that this GPG key is, in fact, valid?

As requested, below is the output from the sudo apt-get -o Debug::Acquire::gpgv=true update command, on both platforms:

• Jessie debug output
• Stretch debug output