This bug was originally reported as http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=492447 by Saku Ytti; I'm just passing it on since I don't know the plans for VisualHostKey. "It might be interesting, if VisualHostKey would use more geometrically connecting characters. Such as, say if we printed character -, it could be followed to the right, by only \, /, -, ., ) etc. Anything that would make it appear as consistent picture to human eye. Also I'd like to believe most terminals are capable of ANSI colours, so that could add accuracy of the identification in very cheap manner, but the colours would need to be also locked to the neighbouring colours, so that it would produce consistent colour theme, instead of random cacophony. Perhaps it could be -o VisualHostKey=colour."
As for the geometrically connected characters: No, you would lose information if you would downgrade to them. The characters are not there to be just eye candy, but they show you different levels of augmentation, i.e. where the worm walked once, twice and so on. You can't give this up without seriously losing information. And as for ANSI colours: No as well. The algorithm was designed to work on the most primitive terminals by purpose, and I don't see that adding colors here would be a very consistent way of design either, regarding the whole OpenSSH project. OpenSSH does not use colors anywhere else for good reason, and so does the randomart algorithm. I am afraid that at least I won't perform any of the enhancements you proposed.
Close bugs fixed/reviewed for openssh-5.2 release