Addendum: You need to set a strict dmarc policy for the checks to fail.
Interestingly, the sites will tell you all three are correct and valid, but still fail the mail.. This is probably due to different pieces of software doing the dns record checking and the email validation.
Verifiers MUST be able to validate signatures with
keys ranging from 512 bits to 2048 bits, and they MAY be able to
validate signatures with larger keys.
I did my master thesis on this topic one year ago and found that all popular mail providers nowadays support 4096 bits, and some even up to 16384 bits.
Unfortunately MAY is not MUST. When it comes to RFCs, it's all too common that people won't implement MAYs, and you should operate expecting that. I wouldn't trust any key over 2048 bits to work.
Provision a 4096-bit DKIM key.
Every online DKIM/SPF checker will say all is good when looking at your DNS.
They will also fail any test email you send, with more or less excellent descriptions such as:
STATUS: Fail
DKIM: Pass
SPF: Pass
There's this fun thing that, apparently:
It's permitted and valid to use keys larger than 2048 bits in your DKIM entry.
It is not, however, required to process keys larger than 2048 bits.
This cost me some hair to learn the hard way.