That sounds way too long. Mine takes like 15 ms on a 2015 cpu and I activate zsh-syntax-highlighting and new style completion and everything, but yeah oh-my-zsh often adds nutso overhead. Anyway, I suggest you profile your zsh start-up. Here's one copy-paste friendly way to do that:

    (PS4='+$EPOCHREALTIME ' zsh -licx exit)2>err
    era=$(grep '^+[1-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9].[0-9]*' <err |
      head -c6) # c6 here rounds to 100_000 seconds (eg +17483xxxyy)
    awk '/^\'${era}'[0-9][0-9][0-9][0-9][0-9]\.[0-9]*/{
         if (c) printf "%.06f %s\n", $1 - t0, c; t0 = $1; c = $0 }
         END { printf "%.06f %s\n", 0, c; }' < err | sort -g > startup-profile

(Note for $EPOCHREALTIME to work you need a `zmodload zsh/datetime` somewhere early on. I might suggest at the top of `$ZDOTDIR/.zshenv` for this kind of thing.)

Also, if something seems limited by "just parsing", you can usually speed that up a lot with `zcompile`. I do that with a `.zcompdump.zwc` and a `digraphs.zsh.zwc`.

EDIT: I noticed myself that really large HISTSIZE (in the 100s of thousands, and with such limit realized) combined with de-duplication seems to be a bad combination. I just lowered my HISTSIZE with a when-too-big spool-off for longer term history/cold storage.