We propose a matrix pencil method for designing one- or two- dimensional (1D or 2D) metalenses with randomly distributed meta-atoms. In contrast to the standard random synthesis algorithm that only randomizes the position of the meta-atoms, the proposed method designs both the position and phase of each meta-atom rigorously. Several all-dielectric random metalenses, in both 1D and 2D operating at 220 GHz, are presented by using our proposed algorithm. Minimum reduction of focusing efficiency can be achieved with respect to a standard metalens with periodically arranged meta-atoms. In contrast to previously reported random metalenses, our random metalenses achieve much higher efficiency, while staying polarization-independent. This synthesis method will pave a way for future random-metasurface-based device designs, which could have more degrees of freedom to information multiplexing.