Social networks often contain sensitive information. Sharing such networks potentially puts the privacy of individuals in the network at risk. Leaving out unique identifiers, i.e., pseudonymization, is insufficient to ensure node anonymity, as the network structure surrounding a node may disclose its identity. The goal of network anonymization is to modify the structure of a given complex network to minimize the number of nodes with a unique neighborhood structure. In the budgeted version of this problem, where a given number of edge modifications is allowed, existing heuristic approaches offer speed but obtain only a limited increase in anonymity. We propose a new simulated annealing approach for network anonymization, SANA, which gradually removes edges from the original network structure to optimize anonymity. Experimental results on real-world social network datasets show that the proposed algorithm outperforms state-of-the-art methods by anonymizing, on average, over 17 times more nodes. Compared to existing approaches, it does so with equal or better data utility after anonymization. The results presented in this work further pave the way for enabling safe and privacy-aware sharing of social network data by researchers and practitioners.