Building on poncho's answer, I believe there's a way to increase the decryption (and encryption) time linearly with minimal ciphertext bloat (e.g. a $k+1$ fold increase using $k$ extra ciphertext bits) and negligible effect on the decryption time variance.
The trick is to append a random $n+k$ secret "tweak" to the passphrase before deriving the message key from it, and including $k$ "hint bits" in the ciphertext, where the $i$-th hint bit is determined by hashing the (possibly salted) passphrase and the first $n+i-2$ bits of the tweak. (Obviously, the ciphertext should also include a regular key check value that depends on the full $n+k$ bit tweak and passphrase.)
This allows the decryptor to interatively reconstruct the tweak using on average $(k+1)2^{n-1}$ hash computations, with a standard deviation of about $2^n/\sqrt{12}$ hash computations regardless of $k$ (as long as $k \ll 2^n$), and $O((n+k)2^{n})$ bits of storage.
Meanwhile, rejecting a wrong passphrase takes on average $(k+2)2^{n-1}$ hash computations, and thus finding the right passphrase from among $N$ choices requires $N(k+2)2^{n-2}$ hash computations on average.
However, I don't think this scheme is actually worth using with $k > 0$. The problem is that, even though the time to reconstruct the message key from a correct passphrase grows in proportion to $k+1$, the average time to test and reject a wrong passphrase grows only in proportion to $k/2+1$.
Thus, let's say we want a brute-force search of an $N$-passphrase space to require about $N2^m$ hash computations on average. We can achieve this by either:
- letting $n = m+1$ and $k = 0$: this makes encryption take only one hash computation and makes decryption take at most $2^{m+1}$ hash computations in the worst case, with an average of $2^m$; or
- letting $n \le m$ and $k = 2^{m-n+2}-2$: this makes encryption take $k+1 = 2^{m-n+2}-1$ hash computations and makes decryption take on average $(k+1)2^{n-1} = 2^{m+1}-2^{n-1}$ hash computations (with a small but non-zero probability of exceeding $2^{m+1}$).
Essentially, for a given target value of $m$, decreasing $n$ and increasing $k$ reduces the variance in decryption time by pushing the average decryption time up towards what would, for $k = 0$, be the worst case. So instead of a random chance of fast (legitimate) decryption, we get guaranteed slow decryption, while the expected speed of a brute-force attack stays the same.
Also, increasing $k$ slows down encryption and makes decryption take exponentially more space. So there really is no advantage to using $k > 0$, and plenty of disadvantages.
(It's possible to do decryption using only constant space even for $k > 0$, by using a depth-first instead of a breadth-first search of the prefix space, but this pushes the standard deviation of encryption time back up to around $(k+1)2^n/\sqrt{12}$ hash evaluations. Of course, a brute-force attacker would almost surely use this method, since they won't care about the variance.)
Furthermore, I strongly suspect that this problem is not specific to this particular scheme, but rather a fundamental limitation. While I haven't managed to formulate a rigorous proof, it seems likely to me that any attempt to reduce the variance of the decryption time below that of the uniform distribution will inevitably either increase the mean decryption time, decrease the mean time for a brute force attack to succeed, or both — and will do so to such a degree that it will effectively negate any possible benefit from the reduced variance.