I just verified that the api key has not changed within the app and also not within Algolia. But since May 10th, I am getting Invalid Application-ID or API key.
Apparently, this was due to transferring ownership. There were Api keys that became inactive. I then used the restore facility and after restoring the missing keys, everything started working again.
Thanks for sharing the resolution here!