After spending some hours to resolve this issue, I was able to make it working again in the Bitrise. I noticed that they mark the existing Apple code signing in each project as legacy and recommend managing it in the workspace settings. After adding my App Store Connect API key there, it started working again with ad-hoc distribution. In my case, I created a new API key, however I hope this helps other devs.

Same issue faced in Bitrise with the api-key code signing, but only ad-hoc distribution. Same api-key with the app-store distribution works as it doesn't require devices. I haven't changed anything and it starts failing with this error from 17. Mar. I am not sure which side causes this issue, however at least there is an incident reported in Bitrise. If anyone uses Bitrise, you can subscribe it to be notified of any updates. https://status.bitrise.io/incidents/2pb4mjklqzz0