Try the context_menu_debug steps from here:
That will usually indicate which part of the context menu is taking a long time.
Although the gif above doesn't look that slow to me. If things are slow only on the first right-click, it's probably due to shell extensions DLLs being loaded for the first time (which also means they're probably being virus scanned).