This paper proposes and proves security of a QKD protocol which uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors. This protocol dramatically outperforms previous QKD protocols for small block sizes. More generally, for the two-universal hashing QKD protocol, the difference between asymptotic and finite key rate decreases with the number $n$ of qubits as $cn^{-1}$, where $c$ depends on the security parameter. For comparison, the same difference decreases no faster than $c'n^{-1/3}$ for an optimized protocol that uses random sampling and has the same asymptotic rate, where $c'$ depends on the security parameter and the error rate.