Online Social Networks (OSN), such as Facebook, Twitter and Tumblr, have revolutionized the way how people share information and stay connected with family and friends. Along this direction, user's privacy has been a significant concern to almost every user in the social network. In this paper, we propose a privacy-aware framework that allows users to outsource their encrypted profile data to a cloud environment. In order to achieve better security and efficiency, our framework utilizes a hybrid encryption approach that consists of Paillier's encryption scheme and AES. Also, we construct a privacy-aware friend recommendation protocol that recommends new friends to a given set of users without compromising their privacy. The proposed protocol adopts a collaborative analysis between the online social network provider and the Cloud in a privacy-preserving manner. Our proposed protocol utilizes the common neighbors approach and additive homomorphic encryption to achieve a reasonable trade-off between accuracy and security. Furthermore, we compared the performance of our protocol with existing work and show that our solution offers better functionality and security. Finally, we present experimental results evaluating the performance of our protocol and demonstrate the practical applicability of our solution.