Image mosaic is a prevalent technique to conceal critical content in images. However, conventional mosaic techniques cannot be recovered using a small-sized key, as they require retransmission of the original images for perfect recovery. In this work, we propose a novel, computationally efficient, and effective recoverable image-mosaic technique. A key advantage of our proposed image-mosaic scheme is its robust performance across a range of adjustable key lengths. Our technique effectively conceals original information even with a small-sized key of only a few bits. To evaluate its performance, we introduce a new image-similarity metric based on the magnitude of the discrete cosine transform (DCT). This metric exhibits several advantageous mathematical properties, including the ability to quantify the perceptibility of major content in mosaicked images, invariance under image reflections and 180-degree rotations, and insensitivity to small translations. Finally, numerical experiments demonstrate that our method outperforms existing recoverable image-mosaic techniques and performs consistent across varying key lengths. We also compare the run-times required by our proposed new scheme with those required by other existing recoverable image-mosaic methods and the state-of-the-art image-encryption methods to exhibit the computational efficiency of our proposed new scheme.