I have encountered the same issue. I have 11,000 posts and it takes roughly 3 minutes to update or add anything. This is not a problem with the pages that I add.
I have the added concern that when I deactivate the plug in my menu does not work (which are linked to post categories). I would like to try the fix that Vali posted above but I am a little concerned about doing that and would rather hear from Yoast about possible answers.
You have an extraordinary plug in. Great work and I hope we can fix the issue soon.
thanks