Hello @Robin Hansson
How many staff ids are you passing to the request? In general more staff ID's would equal a longer time. If still only passing 2/3 at a time their could be issue. In which case I would recommend you raise a support case with Microsoft Graph, a Support Engineer will be able to assist you better. You can raise support ticket from http://aad.portal.azure.com/ or https://admin.microsoft.com/#/support/requests.
Other thing to take into account is if doing lots of requests one after another you could be getting throttling in this case looking at the following best practices might help.
Russell
If the answer is helpful, please click Accept Answer and kindly upvote. If you have any further questions about this answer, please click Comment.