Deduplication is a ubiquitous compression technique for cloud storage servers. It reduces storage and bandwidth requirements by avoiding duplicate copies of data. However, developing an encryption scheme for deduplication is a critical challenge because traditional encryption techniques are not compatible with deduplication. The existing state-of-the-art encryption schemes are at risk of brute-force attacks as they use deterministic techniques for key generation. Moreover, the user in the recent schemes suffers from storage overhead of deduplication metadata and encryption keys. In this paper, we introduce a secure and efficient key management scheme for deduplication. In our scheme, the user divides the file into blocks and encrypts each block using a random key. As a result, our scheme protects against brute-force attacks. In addition, the user securely shares the encryption keys on public storage servers with the aid of a private server. As a result, the proposed approach causes lower storage overhead. We implement our scheme in a real cloud scenario and evaluate the performance of our approach in terms of storage and computation overhead.