We have seen this a lot and there are a few factors that affect this. One question is to check and see how many instances of a workflow or workflows you may have running. You can do this by visiting 

https://tenantname.sharepoint.com/sitename/_layouts/15/WorkflowServiceHealth.aspx 

It will take a second to load but will show all instanes of workflows. running. If you have any there, that might be a factor. 

I just checked and there are no started, suspended, or canceled workflows.

Is this a new thing that you have been seeing?

@aak1 not new but something we have seen pop up randomly over the past 10 months. A lot of it has to do with O365 workflow engine etc, but its hard to tell off the bat.

Another suggestion would be to try and mimic the call in a different site collection within your tenant to see if its site specific, workflow specific etc. I know its a bunch of testing but its hard to tell what could cause it to slow down or take a long time when it does actually work at some point.

I'm testing it on a very basic workflow in another site collection. It also seems to be taking a long time to start.

@aak1 If this is seeming to be timing issue please log into customer.nintex.com or hit the customer central link to the left and create a case there regarding this issue. 

Will do. Thanks.