Discuss and learn French: French vocabulary, French grammar, French culture etc.
Je suis de Colombie is right but I think, even if it's more formal, you'd rather say Je suis originaire de Colombie or Je viens de Colombie.
In general with feminine countries, you just use de (rather than "de la") if you're talking about the country as in the actual geographical region. So: de France, de Colombie, d'Angleterre etc. With a masculine country, on the hand, you would say du Canada, du Congo etc.
On the other hand, if you're talking about the country referring to the people, you would generally use de la.
So for example:
J'ai reçu una carte de Colombie.
L'ONU n'a pas reçu de réponse de la Colombie sur les mesures proposées.
Here, by "from Colombia" we man "from that geographical place" in the first case, but in the second what is actually meant is "from the Colombian people". So in this latter case, speakers would tend to use de la rather than just de.