I see several advantages of mastering the proof of correctness and complexity of an algorithm. I list them below and illustrate with a concrete example. I tried to stay in the domain of classical textbook algorithms.
Understanding why the algorithm works
Certainly the most obvious reason of having proofs. Many algorithms exploit some structure in the problem in a non obvious way. Without proving their correction, there is no way to really understand why it works. Without understanding this, there is no way of really implementing it.
One example of such algorithm is the Blossom algorithm (wikipedia) to find a maximum matching. The idea is to start from an empty matching and iteratively transform it by mixing it with a kind of path called augmented path. When no such path exist anymore, the matching is maximal. One could argue that this algorithm can be implemented without really understanding why it works but finding an augmenting path is not completely obvious and one really need a precise grasp of the object to make it work without bug.
Dynamic programming algorithms also fall into this category. The change-making problem (wikipedia) is a good illustration of that. You have to be careful in defining the relation between the different records so that you are sure it works. The problem is actually also interesting because for some input, greedy approaches work. The fact that it works with the coin systems student are familiar with could mislead them to believe it will always work. Without proofs, people could be tempted to implement a wrong algorithm.
Mastering an algorithm to make variations
Mastering a good toolbox of classical algorithms is essential to be able to design your own efficient algorithms. Knowing techniques such as binary search, fast exponentiation is inspiring to come up with optimization into more complex problems. Understanding the proof of their correctness or complexity is essential to be able to adapt them correctly in a different framework. This is similar to knowing the proof of a theorem in math. Without the proof, you are forced to use whatever statement of the theorem you were able to find in a textbook. With a proof, you can adapt the theorem, relax some hypothesis sometimes, change the underlying algebraic structure etc.
Binary search (wikipedia) is a good and simple illustration of this fact. By understanding the proof of correctness, you know that you need an notion of order and a sorted array. This could be easily forgotten by someone who does not understand why the algorithm is correct. The proof of complexity is also important: the basic textbook will state that the search does $O(\log n)$ access to the array. But it is misleading and hide the fact that you also do $O(\log n)$ comparisons. Applying binary search for structures where equality is cheap but comparing is expensive tells you that it may be better to do a naive search or use some other techniques. Bloom's filters (wikipedia) are also a good illustration of this fact. You need to understand that the quality of the hash function is primordial in their performances.
Another example: the Bellman-Ford algorithm (wikipedia). It is not too hard to understand why it works. If you do not understand the proof, then it is just a shortest path algorithm. Now, if you understand the proof, you see that by changing the underlying semi-ring, you can compute other quantities such as the sum of weights of all path between two points in a DAG, the number of words of length $k$ accepted by a deterministic finite automaton etc.
Complexity guarantees
Some algorithms work by iteratively applying a function until a fix point is reached, the fix point being the solution to our problem. A proof of correction of these algorithms often gives you an upper bound on the number of needed iterations. Using it gives directly gives you an upper bound on the complexity or trade-off between complexity and quality of approximation. The Newton's method (wikipedia) falls into this category, though it may be too mathematical.
Toward implementations
An algorithm may have many forms. From the general idea to concrete implementation. It is important to understand that they are many stages in the conception of the algorithm. Proving the correctness of each step is a big help to ensure a correct implementation in the end. Many textbook algorithms are not implementations but are given as pseudo-code and they still leave you room for optimization when implementing it. Proving the correctness of the algorithm is only the first step toward an efficient implementation. It gives an overview of the property we need in the data structures, it can reveal parts that could be factorized together and grouped into a subfunction etc.
Dijkstra's algorithm (wikipedia) is a very emblematic example of this fact. You can explain the main ideas before giving the details of each subfunction, before describing the heap datastructure to get good complexity guarantees. To finally converge toward an implementation.
