One reason why this name is so rare in Sweden is probably the fact that Kaja is the Swedish name for the Western Jackdaw (Corvus monedula). There is also a derogatory term "fyllkaja" for someone who is very/often drunk; it literally means "drunk jackdaw" and may be derived from seeing jackdaws behave like drunks after eating molding berries.
This name has been quite popular in Norway, although its popularity is declining.
― Anonymous User 3/5/2012
3
I live in Sweden but I've never met anyone with this name. In fact there is only 88 women named this in Sweden. I haven't heard of anyone named Kaja who is from Scandinavia.