We present a linear-time algorithm for generating random derangements. Several algorithms for generating random derangements have recently been published: They are enhancements of the well-known Fisher-Yates shuffle for random permutations, and use the rejection method. The algorithms sequentially generate random permutations, and therefore pick only derangements by omitting the other permutations. A probabilistic analysis has shown that these algorithms could be run in an amortized linear-time. Our algorithm is the first to achieve an exact linear-time generation of random derangements. We use a computational model such that arithmetic operations and random access for O(log n!) = O(n log n) bits can be executed in constant time. (C) 2016 Elsevier B.V. All rights reserved.