An update: flat out denying network access to syspolicyd using Little Snitch could cut down on the delay. (Yes, syspolicyd does send a network request to apple-cloudkit.com for every single new executable. Denying its access to apple-cloudkit.com only isn't sufficient either since it falls back to IP address directly.) Note that this might not be a great idea, and it still has nonzero cost — a network request has to be made and denied by Little Snitch.

Here's my benchmarking script:

  #!/bin/zsh
  tmpfile=$(mktemp)
  cat >$tmpfile <<EOF
  #!/bin/sh
  echo $RANDOM  # Use a different script each time in case it makes a difference.
  EOF
  chmod +x $tmpfile
  setopt xtrace
  time ( $tmpfile )
  time ( $tmpfile )
  unsetopt xtrace
  rm -f $tmpfile

If your local terminal emulator is immune with "Developer Tools" access (interestingly, toggling it off doesn't bring back the delay for some reason), you should be able to reproduce the delay over ssh.