We designed a complete acquisition-reconstruction framework to reduce the radiation dosage in 3D scanning transmission electron microscopy (STEM). Projection measurements are acquired by randomly scanning a subset of pixels at every tilt-view (i.e., random-beam STEM or RB-STEM ). High-quality images are then recovered from the randomly downsampled measurements through a regularized tomographic reconstruction framework. By fulfilling the compressed sensing requirements, the proposed approach improves the reconstruction of heavily-downsampled RB-STEM measurements over the current state-of-the-art technique. This development opens new perspectives in the search for methods permitting lower-dose 3D STEM imaging of electron-sensitive samples without degrading the quality of the reconstructed volume. A Matlab code implementing the proposed reconstruction algorithm has been made available online.