Hi Roman1 and welcome to the community and the forum.
There have been sporadic cases in the past, though I haven’t heard of others directly linked to Android 13 update, so that may be a coincidence. In at least one case, the fast charging resumed though with a different charger.
You seem to have tried all the solutions I would have suggested. The only additional suggestion I would make is to carefully and thoroughly clean the phone’s USB port using a plastic toothpick to remove lint, vacuum cleaner (small tool brush attachment) and / or compressed air for finer dirt and possibly high-grade or isopropyl alcohol. If you know people with other fast chargers and cables keep trying different combinations as occasions occur.
Two additional points, not solutions but that you might bear in mind: (a) fast charging is best avoided when possible since it stresses the battery more, even if the logic slows the rate once a level of 80% or so is reached ; (b) if you regularly need quick topping up on the go, you might consider using a power bank.
The phone will presumably be out of guarantee by now, though you can always contact FP support contactsupport for a repair quote.