I read that it increases shiny chance starting from level 5 but does it further increases the chance for each level?
EDIT: My previous answer was incorrect
Apparently, yes your search level does increase your shiny chances. But the odds only increase until you have a search level of 40. After that, your odds will always be a 0.5% chance. Still very rare, but it'll be a lot easier to find them (though I personally prefer the Masuda Method cough)
Source: http://bulbapedia.bulbagarden.net/wiki/DexNav#Benefits