The reversible data hiding in encrypted images (RDH-EI) technique has been widely used to achieve privacy protection and convenient management of cloud storage images. The existing RDH-EI methods focus on the embedding capacity, reversibility, and the quality of decrypted images. This paper considers a new performance indicator of RDH-EI, the file size of encrypted images, which directly affects the cloud storage cost of content owner and network transmission efficiency. The goal is to obtain the smallest file size and to vacate sufficient space for data embedding. We propose a multi-MSB compression method that includes three strategies: the iterative MSBs-inversion prediction (IMIP), the adjacent prediction plane XOR (APPX), and the block variable length coding (BVLC). The file size of encrypted images is adaptively minimized while ensuring the format compatibility and lossless reconstruction. An encrypted image is generated by a combination of stream ciphers and bit scrambling to improve the resistance to various attacks such as the cipher-only attack (COA). Experimental results demonstrate that the proposed method has higher embedding capacity and resistance to COA compared with the current state-of-the-art methods for images with different texture complexity. The proposed algorithm can achieve the maximum embedding rate ranging from 0.74 to 4.78 bpp.