ssh is installed in my system.
ssh -V OpenSSH_6.6.1p1 Ubuntu-2ubuntu2, OpenSSL 1.0.1f 6 Jan 2014 But when I try to uninstall it completely using sudo apt-get purge openssh-server it says Package 'openssh-server' is not installed, so not removed. How I can remove it completely? I was having issue SSH login using Ubuntu's terminal - Permission denied (publickey), so I wanted to un-install it and again re-install it.
As suggested by Mark in the answer/comments, I've uninstalled ssh using synaptic package manager, still ssh -V was showing it's there. What might be the issue?
As suggested, again I've reinstalled it, still I'm getting SSH login using Ubuntu's terminal - Permission denied (publickey) issue.
While searching for ssh in synaptic package manager, when ssh is installed, instead of showing ssh meta package, it shows something like the attached image. 
4 Answers
On my system the package openssh-server is not installed, it is called openssh-client
sudo apt-get purge openssh-client If it is still there
dpkg --listfiles openssh-client Will give you the locations and name of all openssh-client packages
After looking around, openssh has many preinstalled packages, removing the client alone did not remove ssh from the system, however here is a way to get rid of it all
First you need synaptic package manager
sudo apt-get install synaptic Open this, enter password and in the search box put ssh, now, you see the package just called ssh ? That is an ssh meta package, uninstalling this should remove ssh from the system completely.
The command ssh is part of the package openssh-client
Therefore remove it with
sudo apt-get purge openssh-client You need to stop the ssh service before un-installing it. Just press Ctrl+Alt+T on your keyboard to open Terminal. When it opens, run the command(s) below:
sudo /etc/init.d/ssh stop or
sudo service ssh stop Then do
sudo apt-get --purge remove openssh-client openssh-server 5You have the client. To be sure, type the following:
dpkg -l | grep openssh-client Note that the client is harmless. It is for you to tunnel into other machines. It doesn't include an SSH server that would give an attacker (or anyone) SSH access to your computer.
2