@Bamboulete
One aspect of PowerApps that is often overlooked is the dependency on the datasource in other places.
The way PowerApps works is that it is always real-time updated. Meaning that, just like Excel (which PowerApps is modeled after), when you update a value in a cell that another cell has a referring formula to (and perhaps that too then has additional formulas from other cells, and so on), ALL the formulas update their information.
Same in PowerApps!
If you update the datasource, and you have other formulas that use the datasource (commonly like your Gallery Items), then that formula must re-evaluate and update.
These type of things cause "unseen" slowness. It appears that the patch function is to blame, but it is really other formulas that rely on the datasource.
The BEST way to pinpoint performance issues is to utilize the monitor tool. There you can see how much time any individual function takes (like your Patch specifically), and then you can see how long any other relying formula takes to update.
As for the update of all items, yes, you can do this, but there are some limitations and depending on the number of records...it still can take a good chunk of time.
If in-app real-time data related to the changes is not needed, then PowerAutomate can be utilized to do the work. It will still take some time, but it will be out of band and not seen from the app perspective.