First: the Constitution explicitly gives the Federal Government the right to suppress an insurrection. The southern states engaged in an insurrection. As Lee's quote makes quite clear, they fully recognized that they were engaged in an insurrection.
Second: If a state and its legislature agree to be bound by the Constitution, then they are bound to it. They have entered into a contract with the United States. Secession without the assent of the United States is an explicit breach of that contract, and is thus insurrection.