I recall it being RNG. But the feeding order is very important. If you mess it up, which is common to happen, you'll end up with different colors.

You can check how each snack affects your color here https://ffxiv.consolegameswiki.com/wiki/Chocobo_Colors. What you need to get soot black is to get your RGB colors to 43 41 35. Since you're loam brown now, then your color is 63 51 41.

I'd recommend pulling put a spreadsheet where you mark your feeding order.