No, I don't think they're interchangeable.
You might say "Ne gravas!" if somebody spilled some milk and are really embarrassed about it, but "No problem!" sounds more like a response to a request to me.
It's a pretty American way of speaking. And as a Southerner, I wouldn't say this either. I'd probably say, "Don't worry about it," or "Whatever" with a ¯_(ツ)_/¯
I have the feeling that this is kind of English-Esperanto. I think that you need to know the use that English speakers make of "totally" in this context (like "at all" in a negative sentence) if you want to understand this sentence. For a speaker of romance languages, for instance, this use of "tute" doesn't make much sense.
True. I trying to figure it out how this sentence is the translation one. It's really weird.