Are you using Business Process Tracking?

We had the same problem, also around 13 minutes per loop iteration. For us it turned out that our Data Explorer instance was stopped and the workflow could not send its metadata to Data Explorer. Each loop it took 13 minutes (probably because of the retries) before it gave up and flow continued.