We construct $\varepsilon$-approximate unitary $k$-designs on $n$ qubits incircuit depth $O(\log k \log \log n k / \varepsilon)$. The depth isexponentially improved over all known results in all three parameters $n$, $k$,$\varepsilon$. We further show that each dependence is optimal up toexponentially smaller factors. Our construction uses $\tilde{{O}}(nk)$ ancillaqubits and ${O}(nk)$ bits of randomness, which are also optimal up to $\log(nk)$ factors. An alternative construction achieves a smaller ancilla count$\tilde{{O}}(n)$ with circuit depth ${O}(k \log \log nk/\varepsilon)$. Toachieve these efficient unitary designs, we introduce a highly-structuredrandom unitary ensemble that leverages long-range two-qubit gates and low-depthimplementations of random classical hash functions. We also develop a newanalytical framework for bounding errors in quantum experiments involving manyqueries to random unitaries. As an illustration of this framework'sversatility, we provide a succinct alternative proof of the existence ofpseudorandom unitaries.