Word Order: To answer your last question first: whether ablative Nātūrā comes first or second in these titles is purely a matter of taste and style, not a matter of significance.
The word order is flexible, and the main noun of the noun phrase governed by dē can be placed either immediately after the preposition - as has been mentioned by others, you can see this in Cicero's dē Nātūrā Deōrum (Concerning the Nature of the Gods); also in St. Augustine's dē Nātūrā Bonī (Concerning the Nature of the Good). Or it can be placed after the genitive that modifies it -- as in Lucretius's dē Rērum Nātūrā (Concerning the Nature of Things, or Concerning Things' Nature if you prefer sticking to the original word order). Both orders are equally grammatical, and changing the order does not change the meaning of the phrase.
More broadly, the issue here is that in Latin possessives are typically handled using a noun or noun-phrase in the genitive case, and Latin's case system allows for a great deal more freedom in word ordering than you see with English's style of possessive particles (where the 's has to precede the rest of the noun phrase that it modifies) or with the prepositional phrases of later Romance languages like Spanish or French (where the de ... phrase usually has to follow the rest of the noun phrase that it modifies). In both cases, there are some syntactical reasons why stronger requirements on word ordering are useful for avoiding confusion, whereas a strongly inflected language like Latin can relax restrictions on word order because more of the syntactic work is done by agreement or disagreement in the case of nouns and modifiers.
Word Choice, Regenerātio, -ōnis; Renovāmen, -inis: These are both fine, in terms of form and meaning. A quick note on the grammar: the forms regenerātiōnis and renovāminis here are indeed the correct forms to use in this context. But you describe this as "forming adjectives from nouns," which is not quite right. Regenerātiōnis and renovāminis are still nouns, not adjectives; what you've done (correctly!) is decline the nouns in the genitive singular. In Latin, nouns and noun-phrases in the genitive case typically modify some other noun (for example, nātūrā deī, "the god's nature" or "the nature of the god"), but they do not behave the way that Latin adjectives do (for example, unlike adjectives, you don't make them agree with the noun in case, number or gender). With these two words, you put both nouns into the genitive using the -ōnis/-inis endings because these are 3rd declension nouns, which just means a particular pattern of case/number endings that they share with other nouns like rex, regis, opus, operis, etc. etc. etc.
As far as meaning goes, regenerātiōnis, to a Latin reader, would more strongly suggest rebirth specifically (generō, "I give birth" and genetrix, "birth-giver," "mother," "ancestor" would both be familiar and normal phrases to a Latin reader) and might also tend to carry a strong sense of religious significance (the word most prominently appears in religious writing by the Christian church fathers, for example to describe rebirth in Christ or the "second birth" of baptism). Renovāminis suggests something more like renewal in the sense of change or transformation into a new form or new condition; it is used in Ovid's Metamorphoses to describe what happened when, e.g., girls are transformed into men, or animals, or trees, etc.
Another alternative word you might consider here is renovātiō, -ōnis, which is used in a number of ancient and medieval Latin texts to mean renewal, resumption, renovation or rebuilding -- both in the literal sense (resuming the taking of auspices after they had been neglected; repairing, renovating or rebuilding an old or once-ruined physical building), and also in the metaphorical sense (reviving, reinvigorating, redeeming, restoring, purifying, radically improving or transforming, recreating, etc. an age, a city, an institution, a way of life, or the world as a whole), which appears both in secular and religious writing, and also in both pagan and Christian writers. As with your other two nouns, you would put this into the phrase "Nature of Renewal" by declining it in the genitive singular, as renovātiōnis.
So any of the following might convey your meaning, depending on the details of what connotation, context or shades of significance you want to suggest; the changes in word order do not matter to the meaning, and can be chosen based on whatever you think sounds best in general or in context:
- dē Regenerātiōnis Nātūrā -or- dē Nātūrā Regenerātiōnis
- dē Renovāminis Nātūrā -or- dē Nātūrā Renovāminis
- dē Renovātiōnis Nātūrā -or- dē Nātūrā Renovātiōnis
