First thing first: Can you SSH from a local connection, on the same internal network/segment ? If so, your server is OK. If not, install openssh-server, as previously mentioned. This will also generate local keys and will default to port 22/TCP. This can be changed later.
Second: If you are behind a firewall, can you ssh through it ? or is is right on a public IP address ? If you are on a public, reachable, IP address, and the first point was checked, you should be ready to go. However, there might be other transparent firewalls in the way, and this is out of your hands. The firewall admin will have to change that. get the IP of your own server, and ask that port 22 be open in inbound connection to your new Linux server.
Third: Is your original server using the port 22, or another port ? If using port 22, are you using another port from, say, home ? If so, the firewall would have to get setup to first accept connections on this other port, and redirect those to the proper port of your Linux box. Sometime, those redirections are used so that only certain ports are allowed globally. If you are SSH'ing from another organization, can you ssh to another known box in this same port ?
Many Many Many questions, I know, but those will help you pinpointing the actual problem and ask the right person. or fix the proper setting. The idea here is also to check from the closest connection to the most remote one. As you get further and further, you will be able to see if there is any issue and fix it.