As a small update - I uploaded the same workflow to another gallery as well and there seems to be the same problem regarding performance.
hey @JulianS1
Sorry is this question based on Promote? Or Gallery/Server? I believe it to be Gallery so i'll answer accordingly:
You may be right!
Are you able to run the workflow on the servers designer?
Does it run okay on there?
I suspect it may be a firewall, or the service user does not have access to the sharepoint, maybe try the 'run as' functionality too::
https://help.alteryx.com/current/server/run-workflow-different-user
Hope This Helps!
TheOC