There are two causes to this error.
The Public Key configured in your DNS does not match the Private Key generated/uploaded in Visionflow.
Resolve this by updating the DNS record.
You can verify that the key is correct by using tools such as https://mxtoolbox.com/dkim.aspx & https://www.mail-tester.com/spf-dkim-check
Keep in mind the TTL duration, as it may take some time before the DNS record is updated.
The Public Key is correct but this issue still appears.
This can usually happen when updating an existing DKIM setting with a new key-pair, the Visionflow system will internally remember the old key for the duration of the TTL of the DNS record.
To resolve this issue, you need to wait for the system to clear the DNS record (which contains the Public Key) before it request a new one. Keep in mind that this can sometimes take several hours.