The expected behavior is that it should work once it's accepted the first time. I have a few initial troubleshooting steps I can suggest.
Confirm if the issue is just isolated to the device. If you setup Okta Verify with Push on another Android device with your same user account, does the issue persist? If it does work okay on other devices, then the issue may be isolated to your device.
Confirm if the MFA challenge works the first time without push. Instead of leveraging the push notification, navigate directly to the Okta Verify app and attempt to approve the MFA challenge from there. Does the issue persist, or does it consistantly work the first time?
If the issue is isolated to the device and only when using push, then there may be a configuration issue on the device related to the notifications. Do you experience any other unexpected behavior when using interactive notifications to the device?
Test to see if the issue happens on a known good wireless network and while on the cell network. The results of this test may help identify a connectivity issue. If there is a connectivity issue, it may be the approval of the MFA challenge via the push notification is not consistantly reaching Okta in the cloud and require additional attempts.
Lastly, I'd also recommend trying an uninstall and reinstall of the Okta Verify app and ensure you're on the latest version, and try a reboot of the phone.
If you are still unable to resolve the issue, then I recommend reaching out to Okta Support for additional assistance.