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.